package 算法.排序.快速排序;

import util.SortUtil;

/**
 * 快速排序: 二向切分(普通)
 * 	通过partition() 将某个数j放到数组中的正确位置,并且返回该j	
 * 		j在数组正确位置: j的索引左边的数都比j小, j的索引右边的数都比j大
 *	然后递归，依照上面的逻辑, 对j索引左边的数组 和 右边的数组排序
 *	TODO: 尚未测试。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
 * * @Date 2017-09-11 23：48
 */
public class QuickSort {
	
	public static void sort(int[] arr, int lo, int hi) {
		if (hi <= lo)	return;
		int j = partition(arr, lo, hi);
		sort(arr, lo, j - 1);
		sort(arr, j + 1, hi);
	}
	
	public static int partition(int[] arr, int lo, int hi) {
		int i = lo, j = hi+1;
		int v = arr[lo];
		while (true) {
			while (less(v, arr[++i]))	if (i >= hi)	break;
			while (less(arr[--j], v))	if (j <= lo)	break;
			if (i >= j) 								break;
			exch(arr, i, j);
		}
		exch(arr, lo, j);
		return j;
	}
	
	private static boolean less(int a, int b) {
		if (a > b) 
			return true;
		return false;
	}
	
	private static void exch(int[] arr, int a, int b) {
		int t = arr[a];
		arr[a] = arr[b];
		arr[b] = t;
	}
	
	public static void main(String[] args) {
		QuickSort quickSort = new QuickSort();
		int[] arr = SortUtil.getInitDisorderArr();
		quickSort.sort(arr, 0, arr.length - 1);
	}
}
